package zhengqc.list;

public class SinglyLinkedListR<E> extends AbstractList<E> {
    private class Node {
        public E element;
        public Node next;
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
        public Node(E element) {
            this(element, null);
        }
        public Node() {
            this(null, null);
        }
        @Override
        public String toString() {
            return element.toString();
        }
    }
    /* 单向链表头指针 */
    private Node head;
    /* 删除、获取元素时临时存放在此 */
    private E tempElement;
    private int tempIndex;

    /* 以 node 为头结点的链表中, 在其 index 位置插入元素 element, 递归算法 */
    private Node addNode(Node node, int index, E element) {
        if (index == 0) {
            return new Node(element, node);
        }
        node.next = addNode(node.next, index-1, element);
        return node;
    }

    /* 以 node 为头结点的链表中, 删除其 index 位置元素, 递归算法 */
    private Node removeNode(Node node, int index) {
        rangeCheck(index);
        if (index == 0) {
            /* 将要删除的节点元素保存在此 */
            this.tempElement = node.element;
            return node.next;
        }
        node.next = removeNode(node.next, index-1);
        return node;
    }

    /* 以 node 为头结点的链表中, 设置其 index 位置元素, 使其为 element, 递归算法 */
    private Node setNode(Node node, int index, E element) {
        if (index == 0) {
            node.element = element;
            return node;
        }
        node.next = setNode(node.next, index-1, element);
        return node;
    }

    /* 以 node 为头结点的链表中, 获取其 index 位置元素, 递归算法 */
    private Node getNode(Node node, int index) {
        if (index == 0) {
            this.tempElement = node.element;
            return node;
        }
        ++ this.tempIndex;
        node.next = getNode(node.next, index-1);
        return node;
    }

    /* 以 node 为头结点的链表中, 获取 element 元素的位置, 递归算法 */
    private Node indexOfNode(Node node, E element) {
        if (node == null || node.element.equals(element)) {
            return node;
        }
        ++ this.tempIndex;
        node.next = indexOfNode(node.next, element);
        return node;
    }

    /* 以 node 为头结点的链表中, 将其头结点指向 null , 递归算法 */
    private Node clear(Node node) {
        if (node == null || node.next == null) {
            return null;
        }
        node.next = clear(node.next);
        /* return node; // 错误写法: 这样仅仅可以把最后一个节点删除 */
        return null;
    }

    /* 以 node 为头结点的链表中, 将其后续节点反转, 递归算法 */
    private Node reverse(Node head) {
        if (head == null || head.next == null)
            return head;
        Node newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /* 以 node 为头结点的链表中, 将其后第一个值为 element 的元素删除, 递归算法 */
    private Node removeElement(Node node, E element) {
        if (node == null) {
            return null;
        }
        if (element.equals(node.element)) {
            -- this.size;
            return node.next;
        }
        node.next = removeElement(node.next, element);
        return node;
    }

    /* 以 node 为头结点的链表中, 将其后所有值为 element 的元素删除, 递归算法 */
    private Node removeAllElements(Node node, E element) {
        if (node == null) {
            return null;
        }
        node.next = removeAllElements(node.next, element);
        if (node.element.equals(element)) {
            -- this.size;
            return node.next;
        }
        return node;
    }

    /* 删除单链表中第一个值为 element 的元素 */
    public void removeElement(E element) {
        this.head = removeElement(this.head, element);
    }

    /* 删除单链表中所有值为 element 的元素 */
    public void removeAllElements(E element) {
        this.head = this.removeAllElements(this.head, element);
    }

    /* 反转单链表 */
    public void reverse() {
        this.head = reverse(this.head);
    }

    @Override /* 获取单向链表指定元素的位置 */
    public int indexOf(E element) {
        this.tempIndex = 0;
        indexOfNode(this.head, element);
        return this.tempIndex;
    }

    @Override /* 清空单向链表的所有元素 */
    public void clear() {
        this.head = clear(this.head);
        this.size = 0;
    }

    @Override /* 在单向链表的 index 位置添加元素 element*/
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        this.head = addNode(this.head, index, element);
        ++ this.size;
    }

    @Override /* 在单向链表开始位置添加元素 element*/
    public void addFirst(E element) {
        add(0, element);
    }

    @Override /* 在单向链表末尾位置添加元素 element*/
    public void addLast(E element) {
        add(this.size, element);
    }

    @Override /* 删除单向链表的 index 位置的元素 */
    public E remove(int index) {
        rangeCheck(index);
        this.head = removeNode(this.head, index);
        -- this.size;
        return this.tempElement;
    }

    @Override /* 删除单向链表开始位置的元素 */
    public E removeFirst() {
        remove(0);
        return this.tempElement;
    }

    @Override /* 删除单向链表末尾位置的元素 */
    public E removeLast() {
        remove(this.size-1);
        return this.tempElement;
    }

    @Override /* 设置单向链表 index 位置的元素 */
    public void set(int index, E element) {
        rangeCheck(index);
        this.head = setNode(this.head, index, element);
    }

    @Override /* 获取单向链表 index 位置的元素 */
    public E get(int index) {
        rangeCheck(index);
        this.head = getNode(this.head, index);
        return this.tempElement;
    }

    @Override /* 单向链表转数组 */
    public E[] toArray() {
        E[] array = (E[]) (new Object[this.size]);
        Node current = head;
        for (int i = 0; current != null; ++i) {
            array[i] = current.element;
            current = current.next;
        }
        return array;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("SinglyLinkedListR: size=").append(this.size).append(", content=[");
        Node current = head;
        while (current != null) {
            sb.append(current.element.toString()).append("->");
            current = current.next;
        }
        sb.append("NULL]");
        return sb.toString();
    }
}
